import java.util.Arrays;

public class TestHeap {
    public int[]elem;
    public  int useSize;

    //对elem进行初始化
    public TestHeap(){
        this.elem=new int[10];
    }
    public  void initElem(int[] array){
        for(int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            useSize++;
        }
    }
    public  void createHeap(){
      for(int parent=(this.useSize-1-1)/2;parent>=0;parent--){
          siftDown(parent,this.useSize);
          //parent是每一棵子树调整的时候的起始位置
          //usesize是每一颗子树调整的时候的结束位置
      }
    }

    private void siftDown(int parent, int useSize) {
        int child=2*parent+1;
        while(child<useSize){
            //找打左右孩子的最大值
            if (child+1<useSize&&elem[child]<elem[child]+1) {
                child++;
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                parent=child;
                child=2*parent+1;
            } else {
                break;
            }

        }
    }


    //在堆中插入一个元素
    public  void offer(int val){
        if(isFull()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[useSize]=val;
        useSize++;
        siftUp(useSize-1);

    }
    private  void swap(int [] elem,int child,int parent){
        int tmp=elem[child];
        elem[child]=elem[parent];
        elem[parent]=tmp;
    }

    private void siftUp(int child) {
        int parent=(child-1)/2;
        while(parent>=0) {
            if (elem[child] > elem[parent]) {
               swap(elem,child,parent);
                child = parent;
                parent = (parent - 1) / 2;
            }else {
                break;
            }
        }


    }

    public  boolean isFull(){
        return useSize==elem.length;
    }
    //堆的删除
    public int  poll(){
        if(isEmpty()){
            return -1;
        }
        int val=elem[0];
        swap(elem,0,useSize-1);
        siftDown(0,useSize-1);
        useSize--;
        return val;
    }
    public boolean isEmpty(){
        return useSize==0;
    }
    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return elem[0];
    }
    //对堆进行排序 --》用大根堆进行排序
    public void heapSort(){
        int end=useSize-1;
        while(end>0){
            swap(elem,0,end);
            siftDown(0,end);
            end--;
        }
    }



    //TopK  在堆中找出第K大的数字

}
